package DFSandBFS;
import java.util.*;
/**
 * 判断单词是否存在于二维字符数组中
 * 时间复杂度O(m*n*4^k)，空间复杂度O(k)，m和n为数组的行数和列数，k为单词的长度
 */
public class exist {
    /**
     * 判断单词是否存在于二维字符数组中
     * 
     * @param board 二维字符数组
     * @param word 要查找的单词
     * @return 如果单词存在于数组中，返回true；否则返回false
     */
    public static boolean existM(char[][] board, String word){
        int m = board.length; // 获取数组的行数
        int n = board[0].length; // 获取数组的列数
        int k = 0; // 初始化单词的索引
        for(int i = 0; i < m; i++){ // 遍历数组的每一行
            for(int j = 0; j < n; j++){ // 遍历数组的每一列
                if(backTracking(board, word, i, j, k)) // 调用回溯方法判断单词是否存在
                    return true; // 如果存在，返回true
            }
        }
        return false; // 如果不存在，返回false
    }

    /**
     * 回溯方法，用于判断单词是否存在于二维字符数组中
     * 
     * @param board 二维字符数组
     * @param word 要查找的单词
     * @param i 当前行索引
     * @param j 当前列索引
     * @param k 当前单词的索引
     * @return 如果单词存在于数组中，返回true；否则返回false
     */
    public static boolean backTracking(char[][] board, String word, int i, int j, int k){
        if(i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) // 检查索引是否越界
            return false; // 如果越界，返回false
        // if(board[i][j] == '\0') return false; // 检查当前字符是否已被访问
        if(board[i][j] != word.charAt(k)) return false; // 检查当前字符是否匹配单词的当前字符
        if(k == word.length() - 1) return true; // 如果已经匹配到单词的最后一个字符，返回true
        char tmp = board[i][j]; // 保存当前字符
        board[i][j] = '\0'; // 标记当前字符为已访问
        boolean ans = backTracking(board, word, i + 1, j, k + 1) || // 递归检查上方
                        backTracking(board, word, i - 1, j, k + 1) || // 递归检查下方
                        backTracking(board, word, i, j + 1, k + 1) || // 递归检查右方
                        backTracking(board, word, i, j - 1, k + 1); // 递归检查左方
        board[i][j] = tmp; // 恢复当前字符
        return ans; // 返回结果
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：第一行输入两个整数m和n，表示二维字符数组的行数和列数
     * 接下来m行，每行输入n个字符，表示二维字符数组
     * 最后一行输入一个字符串，表示要查找的单词
     * 输出格式：如果单词存在于数组中，输出true；否则输出false
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); // 读取行数
        int n = sc.nextInt(); // 读取列数
        sc.nextLine(); // 读取换行符
        char[][] board = new char[m][n]; // 创建二维字符数组
        for(int i = 0; i < m; i++){ // 读取每一行的字符
            String[] line = sc.nextLine().split(" "); // 分割输入的字符
            for(int j = 0; j < n; j++){ // 将字符存入数组
                board[i][j] = line[j].charAt(0); // 将字符串转换为字符
            }
        }
        String word = sc.nextLine(); // 读取要查找的单词
        System.out.println(existM(board, word)); // 输出结果
        sc.close(); // 关闭输入流
    }
}
